/*
 * Copyright (c) 1997, 1998, 2003, 2006 Aleksandar Samardzic
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. The name of the author may not be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#include <assert.h>		/* for assert() function */
#include <stdlib.h>		/* for malloc() function */
#include <string.h>		/* for memcpy() function */
#include "heap.h"

/* Heap_Init - Heap class constructor */
void
Heap_Init(this, maxItems, resizeItems, IsLower)
     PHeap          *this;
     int             maxItems;
     int             resizeItems;
     int             IsLower(void *, void *);
{
	this->numItems = 1;

	/* allocate storage for maxItems items */
	this->maxItems = maxItems + 1;
	this->ppItems = malloc(this->maxItems * sizeof(void *));
	assert(this->ppItems != NULL);

	this->resizeItems = (resizeItems == 0) ? 1 : resizeItems;	/* heap 
									 * is 
									 * always 
									 * resizeable 
									 */
	this->IsLower = IsLower;
}

/* Heap_Clean - Heap class destructor */
void
Heap_Clean(this)
     PHeap          *this;
{
	free(this->ppItems);
}

/* Heap_Push - insert item into the heap */
void
Heap_Push(this, pItem)
     PHeap          *this;
     void           *pItem;
{
	void          **ppItems;
	int             index;
	void           *tmp;

	if (this->numItems == this->maxItems) {	/* heap needs to be
						 * extended */
		ppItems =
		    malloc((this->maxItems +
			    this->resizeItems) * sizeof(void *));
		assert(ppItems != NULL);
		memcpy(ppItems, this->ppItems,
		       this->maxItems * sizeof(void *));
		free(this->ppItems);
		this->ppItems = ppItems;
		this->maxItems += this->resizeItems;
	}

	/* insert item at the end of heap */
	this->ppItems[this->numItems] = pItem;

	/* find appropriate position for item */
	for (index = this->numItems; index > 1; index /= 2)
		if (this->
		    IsLower(this->ppItems[index],
			    this->ppItems[index / 2]))
			tmp = this->ppItems[index / 2], this->ppItems[index / 2] = this->ppItems[index], this->ppItems[index] = tmp;	/* move 
																	 * item 
																	 * up 
																	 */
		else
			break;
	(this->numItems)++;
}

/* Heap_Pop - remove item from the top of heap */
void           *
Heap_Pop(this)
     PHeap          *this;
{
	void           *pItem;
	int             index;
	void           *tmp;

	if (this->numItems <= 1)
		return NULL;

	/* remember item at top of heap */
	pItem = this->ppItems[1];

	/* move last item to top */
	this->ppItems[1] = this->ppItems[this->numItems - 1];

	/* find appropriate position for this item */
	for (index = 2; index < this->numItems - 1; index *= 2) {
		if (index < this->numItems - 2)
			index =
			    this->IsLower(this->ppItems[index],
					  this->ppItems[index +
							1]) ? index : index
			    + 1;

		if (this->
		    IsLower(this->ppItems[index],
			    this->ppItems[index / 2]))
			tmp = this->ppItems[index], this->ppItems[index] = this->ppItems[index / 2], this->ppItems[index / 2] = tmp;	/* move 
																	 * item 
																	 * down 
																	 */
		else
			break;
	}

	(this->numItems)--;
	return pItem;
}

/* Heap_IsEmpty - check if there are items in heap */
int
Heap_IsEmpty(this)
     PHeap          *this;
{
	return this->numItems <= 1;
}

/* Heap_First - query first item from heap */
void           *
Heap_First(this)
     PHeap          *this;
{
	if (this->numItems <= 1)
		return NULL;
	return this->ppItems[1];
}
